#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

const int INF = 5000001;
const int EMPTY = 26;

class PalindromizationDiv1 {
public:
	int changeCost[27][27];
	int matchCost[27][27];
	int dp[55][55];
	string word;
	int rec(int, int);
	int getMinimumCost(string, vector <string>);
};

int PalindromizationDiv1::rec(int a, int b){
	int &ret = dp[a][b];
	if(ret != -1) return ret;
	if(a == b) return ret = 0;
	
	int ca = word[a] - 'a';
	int cb = word[b] - 'a';
	if(a == b-1) return ret = matchCost[ca][cb];
	ret = INF;
	
	int x, y;
	
	x = matchCost[ca][cb];
	y = rec(a+1, b-1);
	if(x < ret - y) ret = min(INF, x + y);
//	if(x < ret - y) ret = x + y;	
	
	x = min(matchCost[ca][EMPTY], matchCost[EMPTY][ca]);
	y = rec(a+1, b);
	if(x < ret - y) ret = min(INF, x + y);
//	if(x < ret - y) ret = x + y;	
		
	x = min(matchCost[cb][EMPTY], matchCost[EMPTY][cb]);
	y = rec(a, b-1);
	if(x < ret - y) ret = min(INF, x + y);
//	if(x < ret - y) ret = x + y;		
	return ret;
}

int PalindromizationDiv1::getMinimumCost(string w, vector <string> op) {
//	memset(changeCost, -1, sizeof(changeCost));
//	memset(matchCost, -1, sizeof(matchCost));
	memset(dp, -1, sizeof(dp));
	this->word = w;
	
	for(int i=0; i<27; i++){
		for(int j=0; j<27; j++){
			changeCost[i][j] = INF;
			matchCost[i][j] = INF;
		}
	}
	
	for(int i=0; i<27; i++){
		changeCost[i][i] = 0;
	}
	
	for(int i=0; i<op.size(); i++){
		stringstream s(op[i]);
		string str;
		char ca, cb;
		s >> str >> ca;
//		cout << str << "," << ca << endl;
		if(str == "add") s >> changeCost[EMPTY][ca-'a'];
		else if(str == "erase") s >> changeCost[ca-'a'][EMPTY];
		else {
			s >> cb;
			s >> changeCost[ca-'a'][cb-'a'];
		}
	}
	
	for(int k=0; k<27; k++){
		for(int i=0; i<27; i++){
			for(int j=0; j<27; j++){
				int x = changeCost[i][k];
				int y = changeCost[k][j];
				int &z = changeCost[i][j];
				if(x < z - y) z = min(INF, x+y);
			}
		}
	}
	
//	for(int i=0; i<27; i++){
//		for(int j=0; j<27; j++){
//			cout << changeCost[i][j] << ", ";
//		}
//		cout << endl;
//	}
	
	for(int i=0; i<27; i++){
		for(int j=0; j<27; j++){
			for(int k=0; k<27; k++){
				int x = changeCost[i][k];
				int y = changeCost[j][k];
				int &z = matchCost[i][j];
				if(x < z - y) z = min(INF, x+y);
			}
		}
	}

	for(int i=0; i<27; i++){
		for(int j=0; j<27; j++){
			cout << changeCost[i][j] << ", ";
		}
		cout << endl;
	}
	
	int x = rec(0, word.size()-1);
	return ((x>=INF)? -1 : (int)x);
}


double test0() {
	string p0 = "racecar";
	vector <string> p1;
	PalindromizationDiv1 * obj = new PalindromizationDiv1();
	clock_t start = clock();
	int my_answer = obj->getMinimumCost(p0, p1);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p2 = 0;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p2 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p2 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test1() {
	string p0 = "topcoder";
	string t1[] = {"erase t 1", "erase o 1", "erase p 1", "erase c 1", "erase d 1", "erase e 1", "erase r 1"};
	vector <string> p1(t1, t1+sizeof(t1)/sizeof(string));
	PalindromizationDiv1 * obj = new PalindromizationDiv1();
	clock_t start = clock();
	int my_answer = obj->getMinimumCost(p0, p1);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p2 = 5;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p2 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p2 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test2() {
	string p0 = "topcoder";
	string t1[] = {"erase t 10", "erase o 1", "erase p 1", "erase c 1", "erase d 1", "erase e 1", "erase r 1"};
	vector <string> p1(t1, t1+sizeof(t1)/sizeof(string));
	PalindromizationDiv1 * obj = new PalindromizationDiv1();
	clock_t start = clock();
	int my_answer = obj->getMinimumCost(p0, p1);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p2 = 7;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p2 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p2 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test3() {
	string p0 = "caaaaaab";
	string t1[] = {"change b a 100000", "change c a 100000", "change c d 50000", "change b e 50000", "erase d 50000", "erase e 49999"};
	vector <string> p1(t1, t1+sizeof(t1)/sizeof(string));
	PalindromizationDiv1 * obj = new PalindromizationDiv1();
	clock_t start = clock();
	int my_answer = obj->getMinimumCost(p0, p1);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p2 = 199999;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p2 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p2 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test4() {
	string p0 = "moon";
	string t1[] = {"erase o 5", "add u 7", "change d p 3", "change m s 12", "change n d 6", "change s l 1"};
	vector <string> p1(t1, t1+sizeof(t1)/sizeof(string));
	PalindromizationDiv1 * obj = new PalindromizationDiv1();
	clock_t start = clock();
	int my_answer = obj->getMinimumCost(p0, p1);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p2 = -1;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p2 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p2 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}

int main() {
	int time;
	bool errors = false;
	
	time = test0();
	if (time < 0)
		errors = true;
	
	time = test1();
	if (time < 0)
		errors = true;
	
	time = test2();
	if (time < 0)
		errors = true;
	
	time = test3();
	if (time < 0)
		errors = true;
	
	time = test4();
	if (time < 0)
		errors = true;
	
	if (!errors)
		cout <<"You're a stud (at least on the example cases)!" <<endl;
	else
		cout <<"Some of the test cases had errors." <<endl;
}

//Powered by [KawigiEdit] 2.0!
